/*******************************************************************************

"FreePastry" Peer-to-Peer Application Development Substrate

Copyright 2002-2007, Rice University. Copyright 2006-2007, Max Planck Institute 
for Software Systems.  All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

- Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.

- Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.

- Neither the name of Rice  University (RICE), Max Planck Institute for Software 
Systems (MPI-SWS) nor the names of its contributors may be used to endorse or 
promote products derived from this software without specific prior written 
permission.

This software is provided by RICE, MPI-SWS and the contributors on an "as is" 
basis, without any representations or warranties of any kind, express or implied 
including, but not limited to, representations or warranties of 
non-infringement, merchantability or fitness for a particular purpose. In no 
event shall RICE, MPI-SWS or contributors be liable for any direct, indirect, 
incidental, special, exemplary, or consequential damages (including, but not 
limited to, procurement of substitute goods or services; loss of use, data, or 
profits; or business interruption) however caused and on any theory of 
liability, whether in contract, strict liability, or tort (including negligence
or otherwise) arising in any way out of the use of this software, even if 
advised of the possibility of such damage.

 *******************************************************************************/
package rice.pastry.standard;

import rice.environment.Environment;
import rice.environment.logging.Logger;
import rice.p2p.commonapi.rawserialization.*;
import rice.pastry.*;
import rice.pastry.client.PastryAppl;
import rice.pastry.messaging.*;
import rice.pastry.routing.*;
import uva.MaliciousId;
import uva.MaliciousNodes;
import uva.RoutingTableManager;

import java.io.IOException;
import java.util.*;

/**
 * An implementation of a simple route set protocol.
 * 
 * @version $Id: StandardRouteSetProtocol.java,v 1.15 2005/03/11 00:58:02 jeffh Exp $
 * 
 * @author Andrew Ladd
 * @author Peter Druschel
 */

public class StandardRouteSetProtocol extends PastryAppl implements RouteSetProtocol {
	private final int maxTrials;

	private RoutingTable routeTable;

	private Environment environmet;

	protected Logger logger;

	static class SRSPDeserializer extends PJavaSerializedDeserializer {
		public SRSPDeserializer(PastryNode pn) {
			super(pn);
		}

		public Message deserialize(InputBuffer buf, short type, int priority, NodeHandle sender) throws IOException {
			switch (type) {
			case RequestRouteRow.TYPE:
				return new RequestRouteRow(sender, buf);
			case BroadcastRouteRow.TYPE:
				return new BroadcastRouteRow(buf, pn, pn);
			}
			return null;
		}
	}

	/**
	 * Constructor.
	 * 
	 * @param lh
	 *            the local handle
	 * @param sm
	 *            the security manager
	 * @param rt
	 *            the routing table
	 */
	public StandardRouteSetProtocol(PastryNode ln, RoutingTable rt) {
		this(ln, rt, null);
	}

	public StandardRouteSetProtocol(PastryNode ln, RoutingTable rt, MessageDeserializer md) {
		super(ln, null, RouteProtocolAddress.getCode(), md == null ? new SRSPDeserializer(ln) : md);
		// System.out.println("new SRSP for " + ln.getId());

		this.environmet = ln.getEnvironment();
		maxTrials = (1 << rt.baseBitLength()) / 2;
		routeTable = rt;
		logger = environmet.getLogManager().getLogger(getClass(), null);

	}

	/**
	 * Receives a message.
	 * 
	 * @param msg
	 *            the message.
	 */

	public void messageForAppl(Message msg) {

		boolean logForIvan = false;

		MaliciousNodes maliciousNodes = MaliciousNodes.getInstance();
		boolean areMaliciousNodesActive = MaliciousNodes.getInstance().getAreMaliciousNodesActive();

		boolean shouldGetNew = false;

		if (msg instanceof BroadcastRouteRow) {
			BroadcastRouteRow brr = (BroadcastRouteRow) msg;
			// logger.log("Standard RouteSet Protocol line 113, Received "+brr.toStringFull());

			if (logger.level <= Logger.FINER + 5) {
				// logger.log("Received " + brr.toStringFull());
			}

			RouteSet[] row = brr.getRow();

			NodeHandle rowSender = brr.from();

			boolean isLocalNodeMalicious = maliciousNodes.isPresent(this.thePastryNode.getId());

			int rowMaliciousNodesCount = 0;

			int countMaliciousBefore = maliciousNodes.countMaliciousNodes(this.thePastryNode, logForIvan);

			
//			if (maliciousNodes.isPresent(this.thePastryNode.getId())) {
//				System.out.print(">!" + this.thePastryNode.getId().toStringFull() + "!< ");
//			}
//			else {
//				System.out.print(this.thePastryNode.getId().toStringFull());
//			}
//
//			if (maliciousNodes.isPresent(rowSender.getId())) {
//				System.out.println(" got table row from >!" + rowSender.getId().toStringFull() + "!< : \n");
//			}
//			else {
//				System.out.println(" got table row from " + rowSender.getId().toStringFull() + ": ");
//			}
			//printRow(row, true);

			//System.out.println("end row\n");

//			System.out.println("routing table before received row, main: ");
//			System.out.println(this.thePastryNode.getRoutingTable().printSelf());
//			System.out.println("0:");
//			System.out.println(this.thePastryNode.getRoutingTable().GetUnderlyingTable(0).printSelf());
//			System.out.println("1:");
//			System.out.println(this.thePastryNode.getRoutingTable().GetUnderlyingTable(1).printSelf());
//			System.out.println("2:");
//			System.out.println(this.thePastryNode.getRoutingTable().GetUnderlyingTable(2).printSelf());
			
			if (rowSender.isAlive()) {

//				routeTable.put(rowSender);
				routeTable.put(rowSender, rowSender);
				// System.out.println("");
				// System.out.println("node to put: " + nh.getId().toStringFull()+"\n");
				// System.out.println("after: " + routingTableManager.getTable(index).printSelf());
				//
				// if(!nh.getId().toStringFull().equals(this.thePastryNode.getId().toStringFull())){
				// System.out.println("");
				// }

			}

			if (logForIvan && areMaliciousNodesActive && maliciousNodes.isPresent(rowSender.getId()) && !isLocalNodeMalicious) {
				rowMaliciousNodesCount = maliciousNodes.countMaliciousNodes(row, logForIvan);
				System.out.println("row has " + rowMaliciousNodesCount + " malicious nodes");
			}

			for (int i = 0; i < row.length; i++) {
				RouteSet rs = row[i];

				for (int j = 0; rs != null && j < rs.size(); j++) {
					NodeHandle nh = rs.get(j);
					if (logForIvan) {
						// System.out.print(nh.getId().toStringFull() + " ");
					}

					if (nh.isAlive() == false)
						continue;
					if (logForIvan && areMaliciousNodesActive && maliciousNodes.isPresent(nh.getId()) && !isLocalNodeMalicious) {
						System.out.println("putting a malicious node in: >!" + nh.getId().toStringFull() + "!<");
					}
//					routeTable.put(nh);
					routeTable.put(nh, rowSender);
				}
				if (rs != null && logForIvan) {
					// System.out.print("|");
				}
			}

			int countMaliciousAfter = maliciousNodes.countMaliciousNodes(this.thePastryNode, logForIvan);

			if (logForIvan && shouldGetNew && rowMaliciousNodesCount > countMaliciousAfter) {
				System.out.println("should have received new, but didn't ");
			}

			
//			System.out.println("routing table after received row, main: ");
//			System.out.println(this.thePastryNode.getRoutingTable().GetUnderlyingTable(-1).printSelf());
//			System.out.println("0:");
//			System.out.println(this.thePastryNode.getRoutingTable().GetUnderlyingTable(0).printSelf());
//			System.out.println("1:");
//			System.out.println(this.thePastryNode.getRoutingTable().GetUnderlyingTable(1).printSelf());
//			System.out.println("2:");
//			System.out.println(this.thePastryNode.getRoutingTable().GetUnderlyingTable(2).printSelf());
			

		}

		else if (msg instanceof RequestRouteRow) { // a remote node request one
													// of
													// our routeTable rows
			RequestRouteRow rrr = (RequestRouteRow) msg;

			int reqRow = rrr.getRow();

			// System.out.println("requesting row : " + reqRow);

			NodeHandle nh = rrr.returnHandle();

			RouteSet normalRow[] = routeTable.getRow(reqRow);
			RouteSet rowToSend[] = normalRow.clone();

			if (this.thePastryNode.getIsMalicious() && MaliciousNodes.getInstance().getAreMaliciousNodesActive()) {

				rowToSend = null;
				rowToSend = getMaliciousRow(normalRow, reqRow, rrr);

				if (countMaliciousNodes(rowToSend) < countMaliciousNodes(normalRow)) {
					System.out.println("should not remove malicious nodes");
					System.exit(0);
				}
			}
			BroadcastRouteRow brr = new BroadcastRouteRow(thePastryNode.getLocalHandle(), rowToSend);
			// logger.log("standardRouteSetProtocol line 144: Responding to "+rrr+" with "+brr.toStringFull());

			if (MaliciousNodes.getInstance().getAreMaliciousNodesActive()) {
				// logger.log("Responding to " + rrr + " with " + brr.toStringFull());
			}
			thePastryNode.send(nh, brr, null, options);
		}

		else if (msg instanceof InitiateRouteSetMaintenance) { // request for
																// routing table
																// maintenance

			// System.out.println("initiate maintenance for node: " + this.thePastryNode.getLocalHandle().getId());
			// perform routing table maintenance
			maintainRouteSet();

		}

		else
			throw new Error("StandardRouteSetProtocol: received message is of unknown type");

	}

	/**
	 * performs periodic maintenance of the routing table for each populated row of the routing table, it picks a random column and swaps routing table rows with the closest entry in that column
	 */

	private void maintainRouteSet() {
		// logger.log(
		// "StandardRouteSetProtocol, line 173; maintainRouteSet " +
		// thePastryNode.getLocalHandle().getNodeId());
		if (logger.level <= Logger.INFO)
			logger.log("maintainRouteSet " + thePastryNode.getLocalHandle().getNodeId());

		// for each populated row in our routing table
		for (short i = (short) (routeTable.numRows() - 1); i >= 0; i--) {
			RouteSet row[] = routeTable.getRow(i);
			BroadcastRouteRow brr = new BroadcastRouteRow(thePastryNode.getLocalHandle(), row);
			RequestRouteRow rrr = new RequestRouteRow(thePastryNode.getLocalHandle(), i);
			int myCol = thePastryNode.getLocalHandle().getNodeId().getDigit(i, routeTable.baseBitLength());
			int j;

			// try up to maxTrials times to find a column with live entries
			for (j = 0; j < maxTrials; j++) {
				// pick a random column
				int col = environmet.getRandomSource().nextInt(routeTable.numColumns());
				if (col == myCol)
					continue;

				RouteSet rs = row[col];

				// swap row with closest node only

				if (rs != null && rs.size() > 0) {
					NodeHandle nh;

					nh = rs.closestNode(10); // any liveness status will work

					// this logic is to make this work correctly in the
					// simulator
					// if we find him not alive, then we would have routed to
					// him and the liveness would have failed
					// thus the correct behavior is to break, not continue. In
					// other words, we waste this cycle
					// finding the node faulty and removing it rather than doing
					// an actual swap
					// - Jeff Hoye, Aug 9, 2006
					if (!nh.isAlive()) {
						if (logger.level <= Logger.FINE)
							logger.log("found dead node in table:" + nh);
						rs.remove(nh);
						break;
					}
					// logger.log("swapping with "+(i+1)+"/"+routeTable.numRows()+" "+(j+1)+"/"+maxTrials+":"+nh);

					if (logger.level <= Logger.FINE)
						logger.log("swapping with " + (i + 1) + "/" + routeTable.numRows() + " " + (j + 1) + "/" + maxTrials + ":" + nh);

					/*
					if (MaliciousNodes.getInstance().isPresent(thePastryNode.getId())) {
						System.out.print("pastry node: >!" + thePastryNode.getId().toStringFull() + "!<");
					}
					else {
						System.out.print("pastry node: " + thePastryNode.getId().toStringFull());
					}

					if (MaliciousNodes.getInstance().isPresent(nh.getId())) {
						System.out.println(" sending brr and rrr to >!" + nh.getId().toStringFull() + "!< for row : " + i + " and " + rrr.getRow());
					}
					else{
						System.out.println(" sending brr and rrr to " + nh.getId().toStringFull() + " for row : " + i + " and " + rrr.getRow());
					}*/

					thePastryNode.send(nh, brr, null, options);
					thePastryNode.send(nh, rrr, null, options);
					break;
				}
			}

			// once we hit a row where we can't find a populated entry after
			// numTrial
			// trials, we finish
			if (j == maxTrials) {
				// System.out.println("trials finished after " + maxTrials +
				// " i was "+i);
				// System.out.println(this.routeTable.printSelf());
				break;
			}

		}

	}
	private int countMaliciousNodes(RouteSet[] row) {
		int count = 0;
		for (int i = 0; i < row.length; i++) {
			for (int j = 0; row[i] != null && j < row[i].size(); j++) {
				if (MaliciousNodes.getInstance().isPresent(row[i].get(j).getId())) {
					count++;
				}
			}
		}
		return count;
	}

	private RouteSet[] getMaliciousRow(RouteSet[] row, int reqRow, RequestRouteRow rrr) {
		boolean logForIvan = false;

		RouteSet rowToSend[] = new RouteSet[row.length];

		if (logForIvan) {
			System.out.println("\nrow before:");

			printRow(row, logForIvan);
		}

		copyOverMalicousNodesRemoveNonMalicious(row, rowToSend);

		if (reqRow == this.routeTable.numRows() - 1) {

			getMaliciousTopRow(rowToSend);
		}
		else {
			getMaliciousMiddleRow(rowToSend, reqRow);
		}

		if (logForIvan) {
			// System.out.println("\nrow after:");
			printRow(rowToSend, logForIvan);
		}

		return rowToSend;

		// if (rowToSend[i] != null && logForIvan) {
		// System.out.print(rowToSend[i].get(j).getId().toStringFull() + "|");
		// }
		// else if (logForIvan) {// this happens
		// // when we
		// // had one
		// // node in
		// // the row,
		// // but we
		// // took it
		// // out cause
		// // was not
		// // malicious
		// System.out.print("null|");
		// }
		// if (rowToSend[i] == null && logForIvan) {//this happens when there
		// was nothing in the original row, so we never got in the innner loop
		// System.out.print("null|");
		// }
	}

	private void copyOverMalicousNodesRemoveNonMalicious(RouteSet[] row, RouteSet[] rowToSend) {
		for (int i = 0; i < row.length; i++) {
			for (int j = 0; row[i] != null && j < row[i].size(); j++) {

				if (!checkEvilListForId(row[i].get(j).getId())) {// this is a
																	// non-malicious
																	// node

					if (row[i].size() == 1) {// if we only have a non-malicious
												// node, we'll set the whole row
												// to null,
												// else we will just copy over
												// only the malicious nodes
						rowToSend[i] = null;
					}
					// if we have more than one node, we do nothing

				}
				else {// we have a malicious node in the set, we want
						// to copy it over
					if (rowToSend[i] == null) {
						rowToSend[i] = new RouteSet(row[i].size(), 0, 0, this.thePastryNode);
						// row and column are transient, they aren't serialized
						// anyways
					}

					rowToSend[i].put(row[i].get(j));// add the malicious node to
													// the row
				}
			}
		}
	}

	private void getMaliciousMiddleRow(RouteSet[] rowToSend, int rowIndex) {
		rice.pastry.Id myNodeId = (rice.pastry.Id) this.thePastryNode.getId();

		for (NodeHandle handle : MaliciousNodes.getInstance()) {
			int diffDigit = myNodeId.indexOfMSDD(handle.getNodeId(), this.routeTable.baseBitLength());

			boolean isAlreadyPresentInRow = isPresentInRow(rowToSend, handle.getNodeId());

			if (diffDigit > 0 && rowIndex == diffDigit && !isAlreadyPresentInRow) {
				putMaliciousNodeInRow(rowToSend, handle);
			}
		}
	}

	private void getMaliciousTopRow(RouteSet[] rowToSend) {
		for (int i = 0; i < rowToSend.length; i++) {
			if (rowToSend[i] == null) {// we have a spot in the top row that
										// we can fill

				NodeHandle handle = getMaliciousNodeHandleToSend(rowToSend);
				if (handle == null) {// no more nodes can be added");
					return;
				}
				// System.out.println("a new edge added to top row in node: " + this.thePastryNode.getId().toStringFull() + " in response to " + rrr.getSenderId());
				// System.out.println("old row: ");
				// printRow(rowToSend, true);
				rowToSend[i] = new RouteSet(1, 0, 0, this.thePastryNode);
				rowToSend[i].put(handle);
				// System.out.println("new row: ");
				// printRow(rowToSend, true);
				// System.exit(0);
			}
		}
	}

	private void putMaliciousNodeInRow(RouteSet[] rowToSend, NodeHandle handle) {

		for (int i = 0; i < rowToSend.length; i++) {
			if (rowToSend[i] == null) {
				rowToSend[i] = new RouteSet(this.routeTable.getMaxEntries(), 0, 0, this.thePastryNode);

				rowToSend[i].put(handle);// add the malicious node to

				return;// we put the handle in, go back to caller
			}
		}

	}

	private boolean isPresentInRow(RouteSet[] row, Id maliciousId) {
		for (RouteSet routeSet : row) {
			for (int i = 0; routeSet != null && i < routeSet.size(); i++) {

				if (routeSet.get(i).getId().toStringFull().equals(maliciousId.toStringFull())) {
					return true;
				}
			}

		}

		return false;
	}

	private NodeHandle getMaliciousNodeHandleToSend(RouteSet[] row) {

		boolean isPresent = false;
		MaliciousNodes maliciousNodes = MaliciousNodes.getInstance();
		for (int j = 0; j < maliciousNodes.size(); j++) {
			for (RouteSet routeSet : row) {
				for (int i = 0; routeSet != null && i < routeSet.size(); i++) {

					if (routeSet.get(i) != null) {

						String alreadyPresentId = routeSet.get(i).getId().toStringFull();
						if (maliciousNodes.get(j).getId().toStringFull().equals(alreadyPresentId)) {
							isPresent = true;
						}
					}
				}
			}

			if (j < maliciousNodes.size() && isPresent) {
				isPresent = false;
			}
			else if (j < maliciousNodes.size() && !isPresent) {
				return maliciousNodes.get(j);
			}
		}

		return null;
	}

	private void printRow(RouteSet[] row, boolean logForIvan) {

		for (int i = 0; i < row.length; i++) {

			for (int j = 0; logForIvan && row[i] != null && j < row[i].size(); j++) {
				if (MaliciousNodes.getInstance().isPresent(row[i].get(j).getId())) {
					System.out.print(">!" + row[i].get(j).getId().toStringFull() + "!<|");
				}
				else {
					System.out.print(row[i].get(j).getId().toStringFull() + "|");
				}
			}
			if (logForIvan && row[i] == null) {
				System.out.print("null|");
			}
		}

		if (logForIvan)
			System.out.println("");
	}

	private boolean checkEvilListForId(rice.p2p.commonapi.Id id) {

		return MaliciousNodes.getInstance().isPresent(id);
	}

	

	public boolean deliverWhenNotReady() {
		return true;
	}

}
